﻿/**	@file		std_list.hpp
 *	@date		(2007-07-02 20:15:08)/(2014-11-16 13:59:43)
 *-----------------------------------------------------------------------------
 *	@version	1.0.17.28
 *	@author		Nick Shallery	(nicknide@gmail.com)
 *	@copyright	YOU HAVE ALL LEFT WITH THIS CODE WHILE YOU KEEP COMMENT IN EVERY COPY.
 *-----------------------------------------------------------------------------
**/

#if			!defined(__LOLIX__TOY__STD_LIST__NICK__K_IN_G__)
#define		__LOLIX__TOY__STD_LIST__NICK__K_IN_G__


#if			!defined(__LOLIX__LOLI_X_CFG__K_IN_G__)
	#include	"../lolix_cfg.h"
#endif	//	!defined(__LOLIX__LOLI_X_CFG__K_IN_G__)

#if			!defined(__LOLIX__LOLIX_TYPE__K_IN_G__)
	#include "../lolix_type.h"
#endif	//	!defined(__LOLIX__LOLIX_TYPE__K_IN_G__)

#if			!defined(__LOLIX__TOY_ALLOCATOR__K_IN_G__)
	#include	"./allocator.h"
#endif	//	!defined(__LOLIX__TOY_ALLOCATOR__K_IN_G__)

#if			!defined(__LOLIX__TOY__STD_FUNCTIONAL__NICK__K_IN_G__)
	#include	"./std_functional.hpp"
#endif	//	!defined(__LOLIX__TOY__STD_FUNCTIONAL__NICK__K_IN_G__)

#if			!defined(__LOLIX__TOY__STD_ITERATOR__NICK__K_IN_G__)
	#include	"./std_iterator.hpp"
#endif	//	!defined(__LOLIX__TOY__STD_ITERATOR__NICK__K_IN_G__)

#if			LOLIX_CFG__IS_DEBUG
	#if			!defined(__LOLIX__TOY__L_X_ASSERT_NICK__K_IN_G__)
		#include	"./lx_assert.h"
	#endif	//	defined(__LOLIX__TOY__L_X_ASSERT_NICK__K_IN_G__)

	#define		__LOLIX_LIST_CHECK_VALID(ptr)	do{LOLIX_ASSERT( !(ptr)->_node || !(ptr)->_node->_prv->_nxt, "pre first node lost"); LOLIX_ASSERT((ptr)->_size != size_type(0) - 1, "invalid size"); }while(0)
#else	//	LOLIX_CFG__IS_DEBUG
	#define		__LOLIX_LIST_CHECK_VALID(ptr)
#endif	//	LOLIX_CFG__IS_DEBUG


//==============================================================================
//--------------------------------------------------------------------------
#pragma	pack(push, 8)
namespace lolix{namespace toy{namespace _help{
template<typename _Ty, typename _TAlc>
class	_list_base
{
protected:
	typedef	_list_base<_Ty, _TAlc>	this_type;
	template<typename T, typename for_gcc>
	struct __T_remove_const
		{
		typedef	T	_T_out;
		};
	template<typename T, typename for_gcc>
	struct __T_remove_const<const T, for_gcc>
		{
		typedef	T	_T_out;
		};
	typedef	typename __T_remove_const<typename	_TAlc::template rebind<_Ty>::other, void>::_T_out	_Alc;

	struct	_T_node
	{
		_Ty			_val;
		_T_node*	_nxt;
		_T_node*	_prv;
	};

	template<typename _Cmp>
	class	_T_cmp_node_ptr
	{
		_Cmp _c;
	public:
		typedef _T_node* first_argument_type;
		typedef _T_node* second_argument_type;
		typedef bool result_type;
		_T_cmp_node_ptr(const _Cmp& cp): _c(cp){}

		bool operator()(const _T_node* l, const _T_node* r)
			{
			return _c(l->_val, r->_val);
			}
	};
	typedef	typename _TAlc::template rebind<_T_node>::other	_T_node_alc;
public:
	typedef				_TAlc allocator_type;
	typedef typename	_Alc::size_type			size_type;
	typedef typename	_Alc::difference_type	difference_type;
	typedef typename	_Alc::pointer			pointer;
	typedef typename	_Alc::const_pointer		const_pointer;
	typedef typename	_Alc::reference			reference;
	typedef typename	_Alc::const_reference	const_reference;
	typedef typename	_Alc::value_type		value_type;
private:
	class	_T_CIterator
		{
			typedef	_T_CIterator					this_type;
			friend	_list_base<_Ty, _Alc>;
		protected:
			typedef	_list_base<_Ty, _Alc>	_T_Cnt;
		public:
			//typedef std::bidirectional_iterator_tag iterator_category;
			typedef _Ty								value_type;
			typedef difference_type					difference_type;
			typedef pointer							pointer;
			typedef reference						reference;
			typedef const_pointer					const_pointer;
			typedef const_reference					const_reference;

			LOLIX_INLINE_CALL	_T_CIterator(void)
				: _node(0)
				{
				}
			LOLIX_INLINE_CALL	~_T_CIterator(void){}

			LOLIX_INLINE_CALL	const_reference operator*(void)const
				{
				return __get_ref();
				}

			LOLIX_INLINE_CALL	const_pointer operator->(void)const
				{
				return &__get_ref();
				}

			LOLIX_INLINE_CALL	this_type& operator ++(void)
				{
				LOLIX_ASSERT(_node, L"++ 失败， 当前节点为空， 必须看看， 否则就崩溃了");
				_node = _node->_nxt;
				return *this;
				}

			LOLIX_WARNING_FOR_PERFORMANCE("use prefix increment operator instead")
			LOLIX_INLINE_CALL	this_type operator ++(int)
				{
				this_type tmp(*this);
				++(*this);
				return tmp;
				}

			LOLIX_INLINE_CALL	this_type&	operator --(void)
				{
				if ( !_node )
					{
					_node = _cnt->_node?_cnt->_node->_prv:0;
					return *this;
					}
				LOLIX_ASSERT(*this != _cnt->begin(), L"-- 失败， 当前已经是最前面了， 必须看看");
				_node = _node->_prv;
				return *this;
				}

			LOLIX_WARNING_FOR_PERFORMANCE("use prefix decrement operator instead")
			LOLIX_INLINE_CALL	this_type	operator --(int)
				{
				this_type tmp(*this);
				--(*this);
				return tmp;
				}

#undef		__LOLIX__TMP__DEFINE__LOGIC_CMP_FUNC
#define		__LOLIX__TMP__DEFINE__LOGIC_CMP_FUNC(__lx_v__)		\
			LOLIX_INLINE_CALL	bool operator __lx_v__ (const this_type& o)const{LOLIX_ASSERT(_cnt == o._cnt, L"不同的容器的迭代器比较"); return this->_node __lx_v__ o._node;}
			__LOLIX__TMP__DEFINE__LOGIC_CMP_FUNC(==);
			__LOLIX__TMP__DEFINE__LOGIC_CMP_FUNC(!=);
#undef		__LOLIX__TMP__DEFINE__LOGIC_CMP_FUNC

		protected:
			LOLIX_INLINE_CALL	_T_CIterator(const _T_Cnt* cnt, const typename _T_Cnt::_T_node* o)
				: _node(const_cast<typename _T_Cnt::_T_node*>(o))
				, _cnt(const_cast<_T_Cnt*>(cnt))
				{
				}

			LOLIX_INLINE_CALL	const_reference __get_ref(void)const
				{
				//DO_IN_DEBUG_MODEL(__check_valid(0));
				return _node->_val;
				}

			typename _T_Cnt::_T_node*	_node;
			_T_Cnt*						_cnt;
		};

	friend	_T_CIterator;

	class	_T_Iterator
		: public _T_CIterator
		{
			typedef	_T_Iterator		this_type;
			typedef	_T_CIterator	base_type;
			typedef typename _T_CIterator::_T_Cnt	_T_Cnt;
			friend	_T_Cnt;
		public:
			//typedef typename base_type::iterator_category			iterator_category;
			typedef typename base_type::value_type			value_type;
			typedef typename base_type::difference_type		difference_type;
			typedef typename base_type::pointer				pointer;
			typedef typename base_type::reference			reference;
			typedef typename base_type::const_pointer		const_pointer;
			typedef typename base_type::const_reference		const_reference;

			LOLIX_INLINE_CALL	_T_Iterator(void): base_type(){}

			LOLIX_INLINE_CALL	reference operator* (void)const
				{
				return const_cast<reference>(base_type::operator *());
				}

			LOLIX_INLINE_CALL	pointer operator -> (void)const
				{
				return &(**this);
				}
			LOLIX_INLINE_CALL	this_type& operator++ (void)
				{
				base_type::operator++();
				return *this;
				}

			LOLIX_WARNING_FOR_PERFORMANCE("use prefix increment operator instead")
			LOLIX_INLINE_CALL	const this_type operator++(int)
				{
				this_type tmp(*this);
				++*this;
				return tmp;
				}

			LOLIX_INLINE_CALL	this_type& operator-- (void)
				{
				base_type::operator--();
				return *this;
				}

			LOLIX_WARNING_FOR_PERFORMANCE("use prefix decrement operator instead")
			LOLIX_INLINE_CALL	const this_type operator-- (int)
				{
				this_type tmp(*this);
				--*this;
				return tmp;
				}

		private:
			LOLIX_INLINE_CALL	_T_Iterator(_T_Cnt* cnt, typename _T_Cnt::_T_node* o)
				: _T_CIterator(cnt, o)
				{ }

			using base_type::__get_ref;
			LOLIX_INLINE_CALL	reference __get_ref(void)
				{
				return const_cast<reference>(base_type::__get_ref());
				}
		};
	friend	_T_Iterator;

public:
	typedef	_T_CIterator	const_iterator;
	typedef	_T_Iterator		iterator;
	typedef	lolix::toy::reverse_iterator<iterator>			reverse_iterator;
	typedef	lolix::toy::reverse_iterator<const_iterator>	const_reverse_iterator;
protected:
	LOLIX_INLINE_CALL	_list_base<_Ty, _TAlc>(void):_size(0), _node(0), _alc_node(), _alc_val(){}
	LOLIX_INLINE_CALL	_list_base<_Ty, _TAlc>(const _TAlc& alc):_size(0), _node(0), _alc_node(alc), _alc_val(alc){}
	LOLIX_INLINE_CALL	_list_base<_Ty, _TAlc>(size_type cnt)
		: _alc_node()
		, _alc_val()
		{
		value_type tmp;
		__Construct_by_range(make_value_iterator(_Ty()), make_value_iterator(&tmp, cnt), 0);
		__LOLIX_LIST_CHECK_VALID(this);
		}

	LOLIX_INLINE_CALL	_list_base<_Ty, _TAlc>(size_type cnt, const _Ty& o)
		: _alc_node()
		, _alc_val()
		{
		__Construct_by_range(make_value_iterator(o), make_value_iterator(&o, cnt), make_value_iterator(&o) );
		__LOLIX_LIST_CHECK_VALID(this);
		}

	LOLIX_INLINE_CALL	_list_base<_Ty, _TAlc>(size_type cnt, const _Ty& o, const _TAlc& alc)
		: _alc_node(alc)
		, _alc_val(alc)
		{
		__Construct_by_range(make_value_iterator(o), make_value_iterator(&o, cnt), 0);
		__LOLIX_LIST_CHECK_VALID(this);
		}

	LOLIX_INLINE_CALL	_list_base<_Ty, _TAlc>(const this_type& o)
		: _alc_node(o._alc_node)
		, _alc_val(o._alc_val)
		{
		__Construct_by_range(o.begin(), o.end(), 0);
		__LOLIX_LIST_CHECK_VALID(this);
		}

#if			LOLIX_CFG__SUPPORT_CPP_0X
	LOLIX_INLINE_CALL	_list_base<_Ty, _TAlc>(this_type&& o)
		: _alc_node(forward<_T_node_alc>(o._alc_node))
		, _alc_val(forward<_Alc>(o._alc_val))
		, _node(o._node)
		, _size(o._size)
		{
		o._size = 0;
		o._node = 0;
		}
#endif	//	LOLIX_CFG__SUPPORT_CPP_0X

	template<typename Ipt>
	LOLIX_INLINE_CALL	_list_base<_Ty, _TAlc>(Ipt b, Ipt e)
		: _alc_node()
		, _alc_val()
		{
		__Construct_by_range(b, e, 0);
		__LOLIX_LIST_CHECK_VALID(this);
		}

	template<typename Ipt >
	LOLIX_INLINE_CALL	_list_base<_Ty, _TAlc>(Ipt b, Ipt e, const _TAlc& alc)
		: _alc_node(alc)
		, _alc_val(alc)
		{
		__Construct_by_range(b, e, 0);
		__LOLIX_LIST_CHECK_VALID(this);
		}

	LOLIX_INLINE_CALL	~_list_base<_Ty, _TAlc>(void)
		{
			this->__Clear_node(_node, 0);
		}
public:
	template<typename Ipt>
	LOLIX_INLINE_CALL	void	assign(Ipt b, Ipt e)
		{
		this_type tmp(b, e, _alc_node);
		this->swap(tmp);
		}
	LOLIX_INLINE_CALL	void	assign(size_type cnt, const _Ty& v)
		{
		return assign( make_value_iterator(v), make_value_iterator(v, cnt) );
		}
	LOLIX_INLINE_CALL	reference	back(void)
		{
		LOLIX_ASSERT(_node && _node->_prv, L"非法的 back");
		__LOLIX_LIST_CHECK_VALID(this);
		return _node->_prv->_val;
		}

	LOLIX_INLINE_CALL	const_reference	back(void)const
		{
		__LOLIX_LIST_CHECK_VALID(this);
		return const_cast<this_type>(this)->back();
		}

	LOLIX_INLINE_CALL	iterator begin(void)
		{
		__LOLIX_LIST_CHECK_VALID(this);
		return iterator(this, _node);
		}

	LOLIX_INLINE_CALL	const_iterator begin(void)const
		{
		return const_iterator(this, _node);
		}
	LOLIX_INLINE_CALL	void	clear(void)
		{
		if ( !_node )
			return;

		__Clear_node(_node, 0);
		_node = 0;
		_size = 0;
		__LOLIX_LIST_CHECK_VALID(this);
		}

	LOLIX_INLINE_CALL	bool	empty(void)const
		{
		return _node?false:true;
		}

	LOLIX_INLINE_CALL	iterator	end(void)
		{
		return iterator(this, 0);
		}

	LOLIX_INLINE_CALL	const_iterator end(void)const
		{
		return const_cast<this_type*>(this)->end();
		}

	LOLIX_INLINE_CALL	iterator erase(iterator iter)
		{
		if ( _node->_nxt )
			{
			if ( _node == iter._node )	//	xX
				_node = _node->_nxt;
			else						//	XxX  or Xx
				iter._node->_prv->_nxt = iter._node->_nxt;

			if ( iter._node->_nxt )		//	XxX or xXX
				iter._node->_nxt->_prv = iter._node->_prv;
			else						//	Xx
				_node->_prv = iter._node->_prv;
			}
		else
			_node = 0;
		//	仅仅只有一个

		_T_node* const nxt = iter._node->_nxt;
		_alc_node.destroy(iter._node);
		_alc_node.deallocate(iter._node, 1);

		if ( _size /*|| !_node */)
			--_size;

		__LOLIX_LIST_CHECK_VALID(this);
		return iterator(this, nxt);
		}

	LOLIX_INLINE_CALL	iterator erase(iterator in_b, iterator in_e)
		{
		__Cut_node(in_b._node, in_e._node);
		size_type clr_size = __Clear_node(in_b._node, in_e._node);
		if ( _size || !_node )
			_size -= clr_size;
		else
			_size = 0;

		__LOLIX_LIST_CHECK_VALID(this);
		return in_e;
		}

	LOLIX_INLINE_CALL	reference	front(void)
		{
		LOLIX_ASSERT(_node, L"front 所引用的对象为空, 悬挂引用");
		__LOLIX_LIST_CHECK_VALID(this);
		return _node->_val;
		}
	LOLIX_INLINE_CALL	const_reference	front(void)const
		{
		__LOLIX_LIST_CHECK_VALID(this);
		return const_cast<this_type*>(this)->front();
		}
	LOLIX_INLINE_CALL	const _Alc& get_allocator(void)const
		{
		return _alc_val;
		}

	LOLIX_INLINE_CALL	iterator insert(iterator p, const _Ty& v)
		{
		__LOLIX_LIST_CHECK_VALID(this);
		return insert(p, 1, v);
		}

	LOLIX_INLINE_CALL	iterator insert(iterator p, size_type cnt, const _Ty& v)
		{
		__LOLIX_LIST_CHECK_VALID(this);
		return insert(p, make_value_iterator(v, 0), make_value_iterator(v, cnt));
		}


	template <typename Ipt>
	LOLIX_INLINE_CALL	iterator insert(iterator p, Ipt f, Ipt e)
		{
		//	0:	^
		//	1:	XX^XX
		//	2:	^XXX
		//	3:	XXX^
		size_type new_size;
		_T_node* new_node_front;
		if ( _size )
			new_node_front = __Buy_new_node(f, e, &_size);
		else
			new_node_front = __Buy_new_node(f, e, &new_size);

		if ( !new_node_front )
			return this->end();

		_T_node* new_node_back = new_node_front->_prv;

		_T_node* pos = p._node;
		if ( pos == _node )
			{	//	0, 2
			if ( _node )//	2
			{
				new_node_front->_prv = _node->_prv;
				_node->_prv = new_node_back;
			}

			new_node_back->_nxt = _node;
			_node = new_node_front;
			}
		else
			{	//	1, 3
			new_node_back->_nxt = pos;
			if ( !pos )
				pos = _node;

			pos->_prv->_nxt = new_node_front;
			new_node_front->_prv = pos->_prv;
			pos->_prv = new_node_back;
			}
		__LOLIX_LIST_CHECK_VALID(this);
		return iterator(this, new_node_front);
		}

	LOLIX_INLINE_CALL	size_type	max_size(void)const
		{
		return _alc_node.max_size();
		}

	LOLIX_INLINE_CALL	void	merge(this_type& o)
		{
		__LOLIX_LIST_CHECK_VALID(this);
		return merge(o, less());
		}

	template<typename _Cmp>
	LOLIX_INLINE_CALL	void	merge(size_type& o, const _Cmp& cmp)
		{
		_T_node* first = _node;
		_T_node* second = o._node;

		if ( o._size || !o._node )
			_size += o._size;
		else
			_size = 0;

		o._node = 0;
		o._size = 0;

		if ( !first || !second )
			{
			_node = first?first:second;
		__LOLIX_LIST_CHECK_VALID(this);
			return;
			}

		_T_node* first_back = first->_prv;
		_T_node* second_back = second->_prv;

		_T_node* res = 0;
			{
			_T_node*& tgr(cmp(first->_val, second->_val)?first:second);
			res = tgr;
			tgr = tgr->_nxt;
			}

		_T_node* pos = res;
		while( first && second )
			{
			_T_node*& tgr(cmp(first->_val, second->_val)?first:second);
			pos->_nxt = tgr;
			tgr->_prv = pos;
			tgr = tgr->_nxt;
			}

		if ( first )
			{
			pos->_nxt = first;
			res->_prv = first_back;
			}
		else if ( second )
			{
			pos->_nxt = second;
			res->_prv = second_back;
			}
		else
			{
			pos->_nxt = 0;
			res->_prv = pos;
			}
		__LOLIX_LIST_CHECK_VALID(this);
		}


	LOLIX_INLINE_CALL	void	pop_back(void)
		{
		LOLIX_ASSERT(_node, L"在空的链表上执行pop_back 操作, 不管的话马上就会崩溃");
		_T_node* tmp;
		if ( _node->_nxt )
			{
			tmp = _node->_prv;
			_node->_prv = tmp->_prv;
			tmp->_prv->_nxt = 0;
			}
		else
			{
			tmp = _node;
			_node = 0;
			}

		_alc_node.destroy(tmp);
		_alc_node.deallocate(tmp, 1);

		if ( _size || !_node )
			--_size;
		__LOLIX_LIST_CHECK_VALID(this);
		}

	LOLIX_INLINE_CALL	void	pop_front(void)
		{
		_T_node* tmp = _node;
		_node = _node->_nxt;
		if ( _node )
			_node->_prv = tmp->_prv;

		_alc_node.destroy(tmp);
		_alc_node.deallocate(tmp, 1);

		if ( _size /*|| !_node */)
			--_size;
		__LOLIX_LIST_CHECK_VALID(this);
		}

	template <typename _Ts>
	LOLIX_INLINE_CALL	void	push_back(const _Ts& v)
		{
		_T_node* new_node = __Buy_new_node(v);
		new_node->_nxt = 0;
		if ( _node )
			{
			new_node->_prv = _node->_prv;
			new_node->_prv->_nxt = new_node;
			if ( _size )
				++_size;
			}
		else
			{
			_node = new_node;
			_size = 1;
			}

		_node->_prv = new_node;

		__LOLIX_LIST_CHECK_VALID(this);
		}

	template <typename _Ts>
	LOLIX_INLINE_CALL	void	push_front(const _Ts& v)
		{
		_T_node* new_node = __Buy_new_node(v);
		if ( _node )
			{
			new_node->_prv = _node->_prv;
			_node->_prv = new_node;
			if ( _size )
				++_size;
			}
		else
			{
			new_node->_prv = new_node;
			_size = 1;
			}

		new_node->_nxt = _node;
		_node = new_node;

		__LOLIX_LIST_CHECK_VALID(this);
		}

	LOLIX_INLINE_CALL	typename this_type::reverse_iterator	rbegin(void)
		{
		return (this_type::reverse_iterator(end()));
		}
	LOLIX_INLINE_CALL	typename this_type::const_reverse_iterator rbegin(void)const
		{
		return const_cast<this_type>(this)->rbegin();
		}

	LOLIX_INLINE_CALL	void	remove(const _Ty& v)
		{
		__LOLIX_LIST_CHECK_VALID(this);
#if			LOLIX_CFG__SUPPORT_CPP_0X
		this->remove_if([&v](const_reference r){return r == v;});
#else	//	LOLIX_CFG__SUPPORT_CPP_0X
		return this->remove_if(std::bind1st(std::equal_to<_Ty, _Ty>(), v));
#endif	//	LOLIX_CFG__SUPPORT_CPP_0X
		}

	template<typename _Pre>
	LOLIX_INLINE_CALL	void	remove_if(const _Pre& p)
		{
		const iterator iter_end = this->end();
		for ( iterator iter(this->begin()); iter != iter_end; )
			if ( p(*iter) )
				iter = this->erase(iter);
			else
				++iter;
		__LOLIX_LIST_CHECK_VALID(this);
		}

	LOLIX_INLINE_CALL	typename this_type::reverse_iterator rend(void)
		{
		return this_type::reverse_iterator(begin());
		}
	LOLIX_INLINE_CALL	typename this_type::const_reverse_iterator rend(void)const
		{
		return const_cast<this_type*>(this)->rend();
		}

	LOLIX_INLINE_CALL	void	resize(size_type new_size)
		{
		return this->resize(new_size, _Ty());
		}

	LOLIX_INLINE_CALL	void	resize(size_type new_size, const _Ty& v)
		{
		if ( _size == new_size )
			return;

		if ( !_node )
			{
			this->insert(this->end(), new_size, v);
			}
		else
			{
			iterator iter = this->begin();
			iterator iter_end = this->end();
			if ( _size )
				{
				if ( _size < new_size )
					this->insert(iter_end, new_size - _size, v);
				else
					{
					size_type cnt = 0;
					for ( ; iter != iter_end && cnt != new_size; ++iter )
						++cnt;
					this->erase(iter, iter_end);
					}
				}
			else
				{
				size_type cnt = 0;
				for ( ; iter != iter_end && cnt != new_size; ++iter )
					++cnt;

				if ( cnt != new_size )
					{//	less
					this->insert(iter_end, new_size - cnt, v);
					}
				if ( iter != iter_end )
					{	//	large
					this->erase(iter, iter_end);
					}
				}
			}

		_size = new_size;
		__LOLIX_LIST_CHECK_VALID(this);
		}

	LOLIX_INLINE_CALL	void	reverse(void)
		{
		if ( !_node || !_node->_nxt)
			return;
		//	the first
		_T_node* pos_front = _node;
		_T_node* pos_back = _node->_prv;

		iterator iter_end = this->end();
		for ( iterator iter(this->begin()); iter != iter_end; )
			{
			_T_node* tmp = iter._node;
			++iter;
			lolix::swap(tmp->_nxt, tmp->_prv);
			}

		pos_back->_prv = pos_front;
		pos_front->_nxt = 0;
		__LOLIX_LIST_CHECK_VALID(this);
		}

	LOLIX_WARNING_FOR_PERFORMANCE("slower operator, O(n), use empty() instand?")
	LOLIX_INLINE_CALL	size_type	size(void)const
		{
		return __Adjust_size();
		}

	LOLIX_INLINE_CALL	void	sort(void)
		{
		return sort(less());
		}

	template<typename _Cmp>
	LOLIX_INLINE_CALL	void	sort(const _Cmp& cp)
		{
		if ( this->empty() )
			return;
		this->_node = __Sort_node(this->_node, cp);
		__LOLIX_LIST_CHECK_VALID(this);
		}

	LOLIX_INLINE_CALL	void	splice(iterator pos, this_type& o)
		{
		if ( o.empty() )
			return;
		return this->splice(pos, o, o.begin(), o.end());
		}

	LOLIX_INLINE_CALL	void	splice(iterator pos, this_type& o, iterator in_f)
		{
		iterator f(in_f);
		++in_f;
		return this->__Splice(pos, o, f, in_f, true, 1);
		}

	LOLIX_INLINE_CALL	void	splice(iterator pos, this_type& o, iterator f, iterator e)
		{
		return this->__Splice(pos, o, f, e, false, 0);
		}

	LOLIX_INLINE_CALL	void	swap(this_type& o)
		{
		lolix::swap(_alc_node, o._alc_node);
		lolix::swap(_alc_val, o._alc_val);
		lolix::swap(_node, o._node);
		lolix::swap(_size, o._size);
		__LOLIX_LIST_CHECK_VALID(this);
		}

	LOLIX_INLINE_CALL	void	unique(void)
		{
		//	TODO : fix not found std::equal_to, not include the header?
		//	return this->unique(std::equal_to<_Ty>());
		}

	template <typename _BP>
	LOLIX_INLINE_CALL	void	unique(const _BP& p)
		{
		if ( !_node || !_node->_nxt )
			return;

		if ( _size )
			{
			iterator first = begin();
			const iterator last = end();
			iterator after = first;
			for (++after; after != last; )
				if (p(*first, *after))
					after = erase(after);
				else
					first = after
					, ++after
					;
			}
		else
			{
			iterator first = begin();
			const iterator last = end();
			iterator after = first;
			for (++after; after != last; )
				if (p(*first, *after))
					after = erase(after)
					;
				else
					first = after
					, ++after
					;
			}
		__LOLIX_LIST_CHECK_VALID(this);
		}

	LOLIX_INLINE_CALL this_type& operator = (const this_type& o)
		{
		LOLIX_ASSERT(this != &o, L"自我赋值， 性能会有损耗");
		this_type tmp(o);
		tmp.swap(*this);
		__LOLIX_LIST_CHECK_VALID(this);
		return *this;
		}

#if			LOLIX_CFG__SUPPORT_CPP_0X
	LOLIX_INLINE_CALL this_type& operator = (this_type&& o)
		{
		LOLIX_ASSERT(this != &o, L"自我赋值， 错误");
		_size = o._size;
		_node = o._node;
		_alc_node = forward<_T_node_alc>(o._alc_node);
		_alc_val = forward<_Alc>(o._alc_val);
		o._size = 0;
		o._node = 0;
		return *this;
		}
#endif	//	LOLIX_CFG__SUPPORT_CPP_0X

	template<typename _Ov, typename _Oa>
	bool	operator == (const _list_base<_Ov, _Oa>& o)const
		{
		if ( size() != o.size() )
			return false;

		const_iterator iter = begin(), iter_end = end();
		typename _list_base<_Ov, _Oa>::const_iterator oiter = o.begin();
		for ( ; iter != iter_end; ++iter, ++oiter )
			if ( *iter != *oiter )
				return false;

		return true;
		}

	template<typename _Ov, typename _Oa>
	bool	operator != (const _list_base<_Ov, _Oa>& o)const
		{
		return !((*this) == o);
		}

private:
	LOLIX_INLINE_CALL	void		__Modi_size(difference_type modi)
		{
		if ( modi < 0 )
			{
			if ( _size )
				(difference_type&)_size += modi;
			}
		else
			{
			if ( _size || _node )
				_size += static_cast<size_type>(modi);
			}
		}

	template<typename _Cmp>
	LOLIX_INLINE_CALL	static _T_node*	__Sort_node(_T_node* begin_node, const _Cmp& cp)
		{
		if ( !begin_node )
			return 0;
		auto node_val = begin_node;
		auto node = node_val->_nxt;
		if ( !node )
			{
			begin_node->_prv = begin_node;
			return begin_node;
			}
		const auto PTR_SIZE = sizeof(_T_node*);
		lx_u8 buff[5*PTR_SIZE];
		lx_u8* align_buff = static_cast<lx_u8*>(0) + (buff - static_cast<lx_u8*>(0) + PTR_SIZE - 1) /PTR_SIZE * PTR_SIZE;
		_T_node& low_buff(*reinterpret_cast<_T_node*>(align_buff - LOLIX_OFFSET_OF(_T_node, _nxt)));
		_T_node& high_buff(*reinterpret_cast<_T_node*>(align_buff + 2 * PTR_SIZE - LOLIX_OFFSET_OF(_T_node, _nxt)));

		_T_node* low = &low_buff;
		_T_node* high = &high_buff;
		for ( ; node; node = node->_nxt )
			{
			if ( cp(node->_val, node_val->_val) )
				{
				low->_nxt = node;
				node->_prv = low;
				low = node;
				}
			else
				{
				high->_nxt = node;
				node->_prv = high;
				high = node;
				}
			}
		low->_nxt = 0;
		high->_nxt = 0;

		auto low_ret = __Sort_node(low_buff._nxt, cp);
		auto high_ret = __Sort_node(high_buff._nxt, cp);

		if ( low_ret == 0 )
			{
			low_ret = node_val;
			}
		else
			{
			node_val->_prv = low_ret->_prv;
			low_ret->_prv->_nxt = node_val;
			}

		if ( high_ret )
			{
			low_ret->_prv = high_ret->_prv;
			node_val->_nxt = high_ret;
			high_ret->_prv = node_val;
			}
		else
			{
			node_val->_nxt = 0;
			low_ret->_prv = node_val;
			}

		return low_ret;
		}


	LOLIX_INLINE_CALL	void		__Splice(iterator pos, this_type& o, iterator f, iterator e, bool val_size_invalid, size_type val_size)
	{
		if ( this == &o || f == e )
			return;

		if ( o._alc_node == this->_alc_node )
			{
			if ( val_size_invalid )
				{
				o.__Modi_size(-static_cast<difference_type>(val_size));
				this->__Modi_size(static_cast<difference_type>(val_size));
				}
			else
				o._size = _size = 0;

			_T_node* rnode = o.__Cut_node(f._node, e._node);
			if ( !rnode )
				return;

			_T_node* bnode = rnode->_prv;

			//	^XX
			//	X^X
			//	XX^
			if ( _node == pos._node )
				{	//	^XX
				if ( _node )
					{
					rnode->_prv = _node->_prv;
					_node->_prv = bnode;
					}
				bnode->_nxt = _node;
				_node = rnode;
				}
			else
				{
				if ( pos._node )
					{	//	X^X
					rnode->_prv = pos._node->_prv;
					pos._node->_prv->_nxt = rnode;
					bnode->_nxt = pos._node;
					pos._node->_prv = bnode;
					}
				else
					{	//	XX^
					(rnode->_prv = _node->_prv)->_nxt = rnode;
					(_node->_prv = bnode)->_nxt = 0;
					}
				}
			}
		else
			{
			this->insert(pos, f, e);
			o.erase(f, e);
			}
		__LOLIX_LIST_CHECK_VALID(&o);
		__LOLIX_LIST_CHECK_VALID(this);
	}

	LOLIX_INLINE_CALL	size_type	__Clear_node(_T_node* b, _T_node* e)
		{
		size_type clr_size = 0;
		while ( b != e )
			{
			++clr_size;
			_T_node* tmp = b;
			b = b->_nxt;
			_alc_node.destroy(tmp);
			_alc_node.deallocate(tmp, 1);
			}
		return clr_size;
		}

	template<typename Ipt>
	void	__Construct_by_range(Ipt b, Ipt e, decltype(&((*(Ipt*)0) + 5)))
		{
		_size = e - b;
		if ( b == e )
			{
			_node = 0;
			return;
			}

		_T_node* tmp = __Buy_new_node(*b);
		_node = tmp;

		++b;
		for ( ;b != e; ++b )
			{
			_T_node* new_node = __Buy_new_node(*b);
			tmp->_nxt = new_node;
			new_node->_prv = tmp;
			tmp = new_node;
			}

		tmp->_nxt = 0;
		_node->_prv = tmp;
		__LOLIX_LIST_CHECK_VALID(this);
		}

	template<class Ipt>
	void	__Construct_by_range(Ipt b, Ipt e, ...)
		{
		_size = 0;
		if ( b == e )
			{
			_node = 0;
			return;
			}

		_T_node* tmp = __Buy_new_node(*b);
		_node = tmp;

		++b;
		++_size;
		for ( ;b != e; ++b, ++_size )
			{
			_T_node* new_node = __Buy_new_node(*b);
			tmp->_nxt = new_node;
			new_node->_prv = tmp;
			tmp = new_node;
			}

		tmp->_nxt = 0;
		_node->_prv = tmp;
		__LOLIX_LIST_CHECK_VALID(this);
		}

	_T_node* __Buy_new_node(void)
		{
		_T_node* ptr = _alc_node.allocate(1);
		_alc_val.construct(&ptr->_val);
		__LOLIX_LIST_CHECK_VALID(this);
		return ptr;
		}

	template <typename _Ts>
	_T_node* __Buy_new_node(_Ts& o)
		{
		_T_node* ptr = _alc_node.allocate(1);
		_alc_val.construct((_Ty*)((const char*)ptr + LOLIX_OFFSET_OF(_T_node, _val)), o);
		return ptr;
		}

	template<typename Ipt>
	_T_node* __Buy_new_node(Ipt b, Ipt e, size_type* out_value)
		{
		return __Buy_new_node__(b, e, out_value, 0);
		}

	template<typename Ipt>
	_T_node* __Buy_new_node__(Ipt b, Ipt e, size_type* out_value, decltype(e - b)*)
		{
		*out_value += e - b;

		if ( b == e )
			return 0;

		_T_node* first = __Buy_new_node(*b);
		++b;
		_T_node* pos = first;
		while ( b != e )
			{
			_T_node* tmp = __Buy_new_node(*b);
			tmp->_prv = pos;
			pos->_nxt = tmp;
			pos = tmp;

			++b;
			}

		first->_prv = pos;
		__LOLIX_LIST_CHECK_VALID(this);
		return first;
		}

	template<typename Ipt>
	_T_node* __Buy_new_node__(Ipt b, Ipt e, size_type* out_value, ...)
		{
		if ( b == e )
			return 0;

		_T_node* first = __Buy_new_node(*b);
		++b;
		++*out_value;
		_T_node* pos = first;
		while ( b != e )
			{
			_T_node* tmp = __Buy_new_node(*b);
			tmp->_prv = pos;
			pos->_nxt = tmp;
			pos = tmp;

			++b;
			++*out_value;
			}

		first->_prv = pos;
		__LOLIX_LIST_CHECK_VALID(this);
		return first;
		}

	_T_node*	__Cut_node(_T_node* f, _T_node* e)
		{
		//	0	__XX	//	move _node = e
		//	____	//	move _node = e,
		//	X__X	//
		//	X___

		_T_node* last;
		if ( f == _node )
			{
			_node = e;
			if ( e )
				{
				last = e->_prv;
				_node->_prv = f->_prv;
				}
			else
				 last = f->_prv;
			}
		else
			{
			f->_prv->_nxt = e;
			if ( !e )
				e = _node;
			last = e->_prv;
			e->_prv = f->_prv;
			}

		f->_prv = last;
		__LOLIX_LIST_CHECK_VALID(this);
		return f;
		}

	size_type	__Adjust_size(void)const
		{
		if ( !_size )
			_size = lolix::toy::distance(begin(), end());
		__LOLIX_LIST_CHECK_VALID(this);
		return _size;
		}
protected:
	mutable size_type	_size;
	_T_node*	_node;
	_T_node_alc	_alc_node;
	_Alc		_alc_val;
};

}

template<typename _Ty, typename _TAlc = allocator<void> >
class list
	: public _help::_list_base<_Ty, typename _TAlc::template rebind<_Ty>::other>
{
	typedef	list<_Ty, _TAlc>	this_type;
	typedef	_help::_list_base<_Ty, typename _TAlc::template rebind<_Ty>::other> base_type;
public:
	typedef				_TAlc allocator_type;
	typedef typename	base_type::size_type		size_type;
	typedef typename	base_type::difference_type	difference_type;
	typedef typename	base_type::pointer			pointer;
	typedef typename	base_type::const_pointer	const_pointer;
	typedef typename	base_type::reference		reference;
	typedef typename	base_type::const_reference	const_reference;
	typedef typename	base_type::value_type		value_type;
	typedef	typename	base_type::const_iterator	const_iterator;
	typedef	typename	base_type::iterator			iterator;
	typedef	typename	base_type::reverse_iterator	reverse_iterator;
	typedef	typename	base_type::const_reverse_iterator	const_reverse_iterator;

	LOLIX_INLINE_CALL	list(void):base_type(){}
	template<typename _OnePara>
	LOLIX_INLINE_CALL	list(_OnePara& par):base_type(par){}

	LOLIX_INLINE_CALL	list(size_type cnt, const _Ty& o): base_type(cnt, o){}
	LOLIX_INLINE_CALL	list(size_type cnt, const _Ty& o, const _TAlc& alc): base_type(cnt, o, alc){}
	LOLIX_INLINE_CALL	list(const this_type& o):base_type(o){}
#if			LOLIX_CFG__SUPPORT_CPP_0X
	LOLIX_INLINE_CALL	list(this_type&& o):base_type(forward<base_type>(o)){}
#endif	//	LOLIX_CFG__SUPPORT_CPP_0X

	template<typename Ipt>
	LOLIX_INLINE_CALL	list(Ipt b, Ipt e): base_type(b, e){}
	template<typename Ipt >
	LOLIX_INLINE_CALL	list(Ipt b, Ipt e, const _TAlc& alc): base_type(b, e, alc){}

	template<typename _OT>
	LOLIX_INLINE_CALL	this_type& operator = (const typename remove_const<_OT>::_T_out& o)
		{
		base_type::operator = (o);
		return *this;
		}

	LOLIX_INLINE_CALL	this_type& operator = (const this_type& o)
		{
		base_type::operator = (o);
		return *this;
		}
#if			LOLIX_CFG__SUPPORT_CPP_0X
	LOLIX_INLINE_CALL	this_type& operator = (this_type&& o)
		{
		base_type::operator = (forward<base_type>(o));
		return *this;
		}
#endif	//	LOLIX_CFG__SUPPORT_CPP_0X
};

}}

#pragma	pack(pop)

namespace lolix{
	template<typename _Ty, typename _TAlc>
	LOLIX_INLINE_CALL void swap(toy::_help::_list_base<_Ty, _TAlc>& tl, toy::_help::_list_base<_Ty, _TAlc>& tr)
	{ tl.swap(tr); }
	template<typename _Ty, typename _TAlc>
	LOLIX_INLINE_CALL void swap(toy::list<_Ty, _TAlc>& tl, toy::list<_Ty, _TAlc>& tr)
	{ tl.swap(tr); }
	template<typename _Ty, typename _TAlc>
	LOLIX_INLINE_CALL void discard_copy(toy::_help::_list_base<_Ty, _TAlc>& tl, toy::_help::_list_base<_Ty, _TAlc>& tr)
	{ tl.swap(tr); }
	template<typename _Ty, typename _TAlc>
	LOLIX_INLINE_CALL void discard_copy(toy::list<_Ty, _TAlc>& tl, toy::list<_Ty, _TAlc>& tr)
	{ tl.swap(tr); }
}
#undef		__LOLIX_LIST_CHECK_VALID

//--------------------------------------------------------------------------
//==============================================================================
#endif	//	!defined(__LOLIX__TOY__STD_LIST__NICK__K_IN_G__)
